perm filename A20.TEX[106,RWF] blob
sn#807745 filedate 1985-09-20 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00002 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 \magnification\magstephalf
C00008 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
January\or February\or March\or April\or May\or June\or
July\or August\or September\or October\or November\or December\fi
\space\number\day, \number\year}
\baselineskip 14pt
\def\fnc#1{\mathop{\rm #1}\nolimits}
\rm
\line{\sevenrm a20.tex[106,phy] \today\hfill}
\bigskip\noindent
{\bf Successive Approximation} [ITERATIVE REFINEMENT]
The square root algorithm described above is an example of a method of computing
which begins with an approximation to the answer, whether good or poor, and
applies to the approximate answer an operation which is certain to improve it
if it can be improved. For a problem to which the solution is a real number,
the pattern required is:
\smallskip
\disleft 25pt:(1):If $x$ is not the solution, $f(x)$ is closer
to the solution than $x$~is.
\disleft 25pt:(2):If $x$ is the solution, $f(x)=x$.
\disleft 25pt:(3):The function $f$ is continuous.
\smallskip\noindent
Repeated application of $f$ to any starting value can be shown to
approach the solution as closely as desired.
If the solution to a problem is an integer, condition (3) is not required. In
practice, $f(x)$ should be closer to the solution than $x$ is by at least a
substantial constant factor; if $f(x)$ is less than half as far as $x$ from the
solution, thirty or so iterations gives the solution to nine decimal places.
The square root algorithm, with a starting value in error by a factor of~2,
gives the solution, to nine places, in about four iterations.
\smallskip\noindent
{\bf Exercise.}
If $f$ has property (2), and if $|df/dx|<1$, show it has properties (1) and~(3).
\smallskip\noindent
{\bf Exercise.}
Find the positive solution to the equation $ax↑3+bx↑2+cx+d=0$ by using
$f(x)= -(ax↑3+bx↑2+d)/c$. Show that $f$ has the desired properties in an
interval that includes the solution.
(RWF: replace $a$, $b$, $c$, $d$ by appropriate constants.]
\smallskip\noindent
{\bf Exercise.}
Let $x↓0$ and $x↓1$ be any two positive numbers, and $x↓{i+2}=x↓{i+1}+x↓i$
($i≥2$).
Show the ratio $x↓{i+1}/x↓i$ approaches, as a limit, the positive solution of
the equation $x↑2=x+1$.
\smallskip\noindent
(Note: $x↓{i+2}/x↓{i+1}=1+1/(x↓{i+1}/x↓i)$, or $r↓{i+1}=f(r↓i)=1+1/r↓i$.)
\smallskip\noindent
{\bf Exercise.}
$$\vcenter{\halign{$\ctr{#}$\qquad&$\lft{#}$\qquad&$\ctr{#}$\cr
\bullet\cr
\noalign{\bigskip\bigskip}
\bullet&\bullet&\bullet\cr
x&f(x)&r\cr}}$$
\bigskip
The function $g(x)$ has a root at $r$. A common way to find such a root,
given an estimate $x$, is to evaluate the function and its derivative at~$x$,
and use as the next estimate the zero of a linear function tangent to $g$
at~$x$; this gives $f(x)= x-g(x)/g'(x)$.
Find some conditions under which this method can be guaranteed to converge.
\bigskip
\noindent{\bf Solution.}
$$\eqalign{f'&=1-{(g')↑2-gg''\over (g')↑2}={gg''\over (g')↑2}\,;\cr
\noalign{\medskip}
f'&<1\quad\hbox{ if }\quad gg''<(g')↑2\,,
\quad\hbox{ or }\quad
|g|<\left|{(g')↑2\over g''}\right|\,.\cr}$$
\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd
First draft May 16, 1984
\bye